Conjunto finito hereditariamente

En matemáticas y teoría de conjuntos, los conjuntos finitos hereditariamente se definen como conjuntos finitos cuyos elementos son todos conjuntos finitos hereditarios. En otras palabras, el conjunto en sí es finito y todos sus elementos son conjuntos finitos, recursivamente hasta el conjunto vacío.

Definición formal

Una definición recursiva de conjuntos finitos hereditariamente fundamentados es la siguiente:

Caso base: el conjunto vacío es un conjunto finito hereditariamente.

Regla de recursividad: si a₁, ..., a_k son hereditariamente finitos, entonces también lo es {a₁, ..., a_k}.

El conjunto $\{\{\},\{\{\{\}\}\}\}$ es un ejemplo de un conjunto tan finito hereditariamente y también lo es el conjunto vacío $\emptyset =\{\}$ . Por otro lado, los conjuntos $\{7,{\mathbb {N} },\pi \}$ o $\{3,\{{\mathbb {N} }\}\}$ son ejemplos de conjuntos finitos que no son hereditariamente finitos. Por ejemplo, el primero no puede ser hereditariamente finito, ya que contiene al menos un conjunto infinito como elemento, cuando ${\mathbb {N} }=\{0,1,2,\dots \}$ .

Discusión

Un símbolo de la clase es $H_{\aleph _{0}}$ , representando la cardinalidad de cada uno de sus miembros menor que $\aleph _{0}$ . Si $H_{\aleph _{0}}$ es un conjunto y los enunciados sobre cardinalidad dependen de la teoría en contexto.

Biyección de Ackermann

La clase $H_{\aleph _{0}}$ es contable.Ackermann (1937) dio la siguiente biyección natural f de los números naturales a la $H_{\aleph _{0}}$ , conocido como codificación Ackermann. Se define de forma recursiva por

f(2^{a}+2^{b}+\cdots )=\{f(a),f(b),\ldots \}

si a, b, ... son distintos.

Por ejemplo:

f(5)=f(4+1)=f(2^{2}+2^{0})=\{f(2),f(0)\}=\{f(2^{1}),\{\}\}=\{\{f(1)\},\{\}\}=\{\{f(2^{0})\},\{\}\}=\{\{\{f(0)\}\},\{\}\}=\{\{\{\{\}\}\},\{\}\}

Tenemos f (m) ∈ f (n) si y solo si el m-ésimo dígito binario de n (contando desde la derecha comenzando en 0) es 1.

Representación

Esta clase de conjuntos se clasifica naturalmente por el número de pares de corchetes necesarios para representar los conjuntos:

$\{\}$ (es decir $\emptyset$ , es decir, el ordinal de Neumann "0"),
$\{\{\}\}$ (es decir $\{\emptyset \}$ , es decir Neumann ordinal "1"),
$\{\{\{\}\}\}$ ,
$\{\{\{\{\}\}\}\}$ y luego también $\{\{\},\{\{\}\}\}$ (es decir Neumann ordinal "2"),
$\{\{\{\{\{\}\}\}\}\}$ , $\{\{\{\},\{\{\}\}\}\}$ tanto como $\{\{\},\{\{\{\}\}\}\}$ ,
...conjunto representado con $6$ pares de soportes,
...conjunto representado con $7$ pares de soportes, p. ej. $\{\{\{\{\{\{\{\}\}\}\}\}\}\}$ o $\{\{\},\{\{\}\},\{\{\{\}\}\}\}$ (es decir Neumann ordinal "3"),
...etc.

De esta forma, el número de conjuntos con $n$ pares de corchetes es^[1] $1,1,1,2,3,6,12,25,52,113,247,548,1226,2770,6299,14426,\dots$

Axiomatizaciones

Teorías de conjuntos finitos

El conjunto $\emptyset$ también representa el primer número ordinal de von Neumann, denotado $0$ . Y, de hecho, todos los ordinales finitos de von Neumann están en $H_{\aleph _{0}}$ y así la clase de conjuntos que representan los números naturales, es decir, incluye cada elemento en el modelo estándar de números naturales. La aritmética de Robinson ya se puede interpretar en ST, la subteoría muy pequeña de $Z^{-}$ con axiomas dados por Extensionalidad, Conjunto Vacío y Adjunción.

En efecto, $H_{\aleph _{0}}$ tiene axiomatizaciones constructivas que involucran estos axiomas y, por ejemplo, Establecer inducción y Reemplazo.

Entonces, sus modelos también cumplen los axiomas que consisten en los axiomas de la teoría de conjuntos de Zermelo-Fraenkel sin el axioma de infinito. En este contexto, se puede agregar la negación del axioma del infinito, probando así que el axioma del infinito no es una consecuencia de los otros axiomas de la teoría de conjuntos.

ZF

Los conjuntos finitos hereditariamente son una subclase del universo de Von Neumann. Aquí, todos los conjuntos finitos hereditariamente bien fundados se denotan V_ω. Tenga en cuenta que este es un conjunto en este contexto.

Si denotamos por ℘(S) el conjunto de potencias de S, y por V ₀ el conjunto vacío, entonces V_ω se puede obtener estableciendo V ₁ = ℘ (V₀), V ₂ = ℘ (V₁) ,..., V_k = ℘ (V_k−1), ... y así sucesivamente.

Por tanto, V_ω se puede expresar como $V_{\omega }=\bigcup _{k=0}^{\infty }V_{k}$ .

Vemos, de nuevo, que solo hay un número contable de conjuntos finitos hereditariamente: V_n es finito para cualquier n finito. Su cardinalidad es ⁿ⁻¹ 2, ver tetración. La unión de innumerables conjuntos finitos es contable.

De manera equivalente, un conjunto es hereditariamente finito si y solo si su cierre transitivo es finito.

Modelos gráficos

La clase $H_{\aleph _{0}}$ se puede ver que está en correspondencia exacta con una clase de árboles enraizados, es decir, aquellos sin simetrías no triviales (es decir, el único automorfismo es la identidad): el vértice de la raíz corresponde al paréntesis de nivel superior $\{\dots \}$ y cada borde conduce a un elemento (otro conjunto similar) que puede actuar como un vértice raíz por derecho propio. No existe ningún automorfismo de este gráfico, correspondiente al hecho de que se identifican ramas iguales (por ejemplo, $\{t,t,s\}=\{t,s\}$ , trivializando la permutación de los dos subgrafos de forma $t$ ). Este modelo gráfico permite una implementación de ZF sin infinito como tipos de datos y, por lo tanto, una interpretación de la teoría de conjuntos en las teorías de tipos expresivos.

Existen modelos de gráficos para ZF y también teorías de conjuntos diferentes de la teoría de conjuntos de Zermelo, como teorías no bien fundamentadas. Dichos modelos tienen una estructura de borde más intrincada.

En la teoría de grafos, el gráfico cuyos vértices corresponden a conjuntos finitos hereditariamente y los bordes corresponden a la pertenencia al conjunto es el gráfico de Rado o gráfico aleatorio.

Véase también

Referencias

↑ «A004111 - OEIS». oeis.org. Consultado el 7 de febrero de 2021.

Ackermann, Wilhelm (1937), «Die Widerspruchsfreiheit der allgemeinen Mengenlehre», Mathematische Annalen 114 (1): 305-315, doi:10.1007/BF01594179 .

Datos: Q5737811

[1] «A004111 - OEIS». oeis.org. Consultado el 7 de febrero de 2021.

[1]